/**
 * 
 */
package solution.misc;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class ContiguousIncreasingSubarray {

	int maxLength(int[] arr) {
		if (arr.length < 2)
			return arr.length;

		// at least, the length of contiguous incremental sequence is 1.
		int maxLen = 1;

		// checking using the known maximum length
		for (int i = maxLen; i < arr.length; i += maxLen) {
			// i-maxLen is the starting position of the sequence, so,
			// invariant: arr[i-maxLen-1] >= arr[i-maxLen]
			if (arr[i - 1] >= arr[i]) {
				continue;
			}

			// potentially, the sequence starting from i-maxLen can be longer.
			int subMax = 1;
			for (int j = i - maxLen + 1; j < arr.length; j++) {
				if (arr[j - 1] >= arr[j]) {
					break;
				}
				subMax++;
			}
			if (subMax > maxLen) {
				// found one, adjust both i and the maximum length
				i = i - maxLen + subMax; // tricky step
				maxLen = subMax;
			}
		}
		return maxLen;
	}

	@Test
	public void test() {
		int arrs[][] = new int[][] {//
		// {maxLen},{sequence}
				{ 1 }, { 1 },// 1
				{ 2 }, { 1, 0, 1, 0, 1, 0 },// 2
				{ 3 }, { 1, 2, 3, 0, 1, 0, 1, 0 },// 3
				{ 4 }, { 1, 0, 1, 0, 1, 2, 3, 0 },// 4
				{ 4 }, { 1, 0, 1, 0, 1, 2, 3 },// 4
				{ 4 }, { 1, 0, 1, 2, 3, 0, 1, 0 },// 4
		};

		for (int i = 0; i < arrs.length; i += 2) {
			Assert.assertEquals(arrs[i][0], maxLength(arrs[i + 1]));
		}
	}
}
